﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0203_FindPaths : IAlgorithm
    {
        // title

        /*
        给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。
        你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
        给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果

        提示：
            1 <= m, n <= 50
            0 <= maxMove <= 50
            0 <= startRow < m
            0 <= startColumn < n
        */

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
        }

        // 算法
        public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn)
        {
            const int MOD = 1000000007;
            int[][] directions = new int[][] {
                new int[]{-1, 0},
                new int[]{1, 0},
                new int[]{0, -1},
                new int[]{0, 1}
            };
            int outCounts = 0;
            int[,] dp = new int[m, n];
            dp[startRow, startColumn] = 1;
            for (int i = 0; i < maxMove; i++)
            {
                int[,] dpNew = new int[m, n];
                for (int j = 0; j < m; j++)
                {
                    for (int k = 0; k < n; k++)
                    {
                        int count = dp[j, k];
                        if (count > 0)
                        {
                            foreach (int[] direction in directions)
                            {
                                int j1 = j + direction[0], k1 = k + direction[1];
                                if (j1 >= 0 && j1 < m && k1 >= 0 && k1 < n)
                                {
                                    dpNew[j1, k1] = (dpNew[j1, k1] + count) % MOD;
                                }
                                else
                                {
                                    outCounts = (outCounts + count) % MOD;
                                }
                            }
                        }
                    }
                }
                dp = dpNew;
            }
            return outCounts;
        }
    }
}
